package swardToOffer.struct_4_tree;
// 面试题36：二叉搜索树与双向链表
// 题目：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求
// 不能创建任何新的结点，只能调整树中结点指针的指向。
// 思路：先序遍历可以将树从小到大进行遍历【左子-根-右子】
//当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。
// 还需要返回链表中的第一个节点的指针。
//根据以上分析，考虑使用中序遍历访问树的各节点 cur ；
// 并在访问每个节点时构建 cur 和前驱节点 pre 的引用指向；
// 中序遍历完成后，最后构建头节点和尾节点的引用指向即可。


class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {
    }

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};

public class ConvertBinarySearchTree {
    Node pre, head;

    public Node treeToDoublyList(Node root) {
        if (root == null) return null;
        dfs(root);
        head.left = pre;
        pre.right = head;
        return head;
    }

    private void dfs(Node cur) {
        if (cur==null) return;
        dfs(cur.left);
        if (pre!=null) pre.right = cur;
        else head = cur;
        cur.left = pre;
        pre = cur;
        dfs(cur.right);
    }
}
